package offer.nowcoder.array;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * https://www.nowcoder.com/practice/623a5ac0ea5b4e5f95552655361ae0a8?tpId=13&tqId=11203&tPage=1&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&from=cyc_github&tab=answerKey
 * @author DengYuan2
 * @create 2021-02-08 21:43
 */
public class n_3 {
    public static void main(String[] args) {
//        int[] a ={2,3,1,0,2,5,3};
        int[] a ={6,3,2,0,2,5,0};
        int[] dup = new int[1];
        boolean res = duplicate3(a, 7, dup);
        System.out.println(res);
        System.out.println(Arrays.toString(dup));
    }

    /**
     * 我的写法-用了set
     * 嗨呀，其实完全不用，对数组进行操作即可啊
     * @param numbers
     * @param length
     * @param duplication
     * @return
     */
    public static boolean duplicate(int numbers[],int length,int [] duplication) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < length; i++) {
            int number = numbers[i];
            if (set.contains(number)){
                duplication[0]= number;
                return true;
            }else {
                set.add(number);
            }

        }
        return false;
    }

    /**
     * 将值放到正确的位置，如该位置已有正确的数字，则视为重复，否则交换即可
     * 注意duplicate3()方法中的错误！！！
     * @param numbers
     * @param length
     * @param duplication
     * @return
     */
    public static boolean duplicate2(int numbers[],int length,int [] duplication) {
        for (int i = 0; i < length; i++) {
            int num=numbers[i];
            if (num!=i){
                if (numbers[num]!=num){
                    int tmp = numbers[num];
                    numbers[i]=tmp;
                    numbers[num]=num;
                }else {
                    duplication[0]=num;
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 这么写是错的！！！
     * 针对 {6,3,2,0,2,5,0},结果是0，而应该是2才对，关键就是while循环那错了，让0提到了前面
     * @param nums
     * @param length
     * @param duplication
     * @return
     */
    public static boolean duplicate3(int[] nums, int length, int[] duplication) {
        if (nums == null || length <= 0)
            return false;
        for (int i = 0; i < length; i++) {
            while (nums[i] != i) {
                if (nums[i] == nums[nums[i]]) {
                    duplication[0] = nums[i];
                    return true;
                }
                swap(nums, i, nums[i]);
            }
        }
        return false;
    }

    private static void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }

    /**
     * 官方解法1：
     * boolean只占一位，所以还是比较省的
     * 用数组记录该值是否被访问过
     * @param numbers
     * @param length
     * @param duplication
     * @return
     */
    public boolean duplicate4(int numbers[], int length, int[] duplication) {
        boolean[] k = new boolean[length];
        for (int i = 0; i < k.length; i++) {
            if (k[numbers[i]] == true) {
                duplication[0] = numbers[i];
                return true;
            }
            k[numbers[i]] = true;
        }
        return false;
    }
}
